A search service, such as an online search engine, search application, or “app,” or application with search capability can monetize its services by selling advertising space to advertisers including marketers, or third-parties. The search service receives revenue from advertisers when an advertisement is displayed along with the search results or when a user selects or clicks on the displayed advertisement. Advertisers paying for ads expect the search service to present the ads with search results from queries that are relevant to the ads. Therefore a goal for any search service is to present relevant advertisements to users thereby increasing the likelihood that the users will interact with the advertisements.
Ad selection algorithms attempt to identify relevant ads by inferring user intent behind the user-submitted queries. But in practice, achieving an accurate understanding of a user's intent behind a query, including a long tail search query, and retrieving ads with both high recall and precision presents a difficult problem for selection algorithms. Moreover the ad selection algorithms also face practical constraints including low computing cost and latency as well as high throughput to serve high volume traffic.